1. Field of the Invention
This invention relates to a coding method of image information or the like.
2. Description of Related Art
For coding a Markov information source, the number line representation coding system is known in which a sequence of symbols is mapped on the number line from 0.00 to 1.0 and its coordinates are coded as code words which are, for example, represented in a binary expression. FIG. 1 is a conceptual diagram thereof. For simplicity a bi-level memoryless information source is shown and the occurrence probability for "1" is set at r, the occurrence probability for "0" is set at 1-r. When an output sequence length is set at 3, the coordinates of each of the rightmost C(000) to C(111) is represented in a binary expression and cut at the digit which can be distinguished each other, and is defined as its respective code words, and decoding is possible at a receiving side by performing the same procedure as at the transmission side.
In such a sequence, the mapping interval A.sub.i, and the lower-end coordinates C.sub.i of the symbol sequence at time i are given as follows:
When the output symbol ai is 0 (More Probable Symbol: hereinafter called MPS), EQU A.sub.i =(1-r)A.sub.i-1 EQU C.sub.i =C.sub.i-1
When the output symbol ai is 1 (Less Probable Symbol: hereinafter called LPS), EQU A.sub.i =rA.sub.i-1 EQU C.sub.i =C.sub.i-1 +(1-r)A.sub.i-1
As described in "an overview of the basic principles of the Q-Coder adaptive binary arithmetic coder (IBM journal of Research and Development Vol. 32, No. 6, November, 1988)", it is considered that in order to reduce the number of calculations such as multiplication, a set of fixed values are prepared and a certain value is selected from among them, not necessarily calculating rA.sub.i-1.
That is, if rA.sub.i-1 of the above-mentioned expression is set at S,
when ai=0, EQU A.sub.i =A.sub.i-1 -S EQU C.sub.i =C.sub.i-1
when ai=1, EQU A.sub.i =S EQU C.sub.i =C.sub.i-1 +(A.sub.i-1 -S).
However, as A.sub.i-1 becomes successively smaller, S is also needed to be smaller in this instance. To keep the calculation accuracy, it is necessary to multiply A.sub.i-1 by the second power (hereinafter called normalization). In an actual code word, the above-mentioned fixed value is assumed to be the same at all times and is multiplied by powers of 1/2 at the time of calculation (namely, shifted by a binary number).
If a constant value is used for S as described above, a problem arises when, in particular, S is large and a normalized A.sub.i-1 is relatively small.
An example thereof is given in the following. If A.sub.i-1 is slightly above 0.5, A.sub.i is very small when ai is an MPS, and is even smaller than the area being given when ai is LPS. That is, in spite of the fact that the occurrence probability of MPS is essentially high, the area allocated to MPS is smaller than that allocated to LPS, leading to an decrease in coding efficiency. If it is assumed that an area allocated to MPS is always larger than that allocated to LPS, since A.sub.i-1 &gt;0.5, S must be 0.25 or smaller. Therefore, when A.sub.i-1 is 1.0, r=0.25, and when A.sub.i-1 is close to 0.5, r=0.5, with the result that the occurrence probability of LPS is considered to vary between 1/4 and 1/2 in coding. If this variation can be made small, an area proportional to an occurrence probability can be allocated and an improvement in coding efficiency can be expected.